//
//  DPDemo.swift
//  swiftDemo
//
//  Created by JIENING ZHANG on 2022/12/2.
//  Copyright © 2022 lovivid. All rights reserved.
//

import UIKit

class DPDemo: NSObject {
    //给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
    // https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484731&idx=1&sn=f1db6dee2c8e70c42240aead9fd224e6&scene=21#wechat_redirect
    
    var amount2minNumDic:[Int:(Int, [Int])] = [:]
    func coinChange(_ coins:[Int], _ amount:Int ) -> (Int, [Int]) {
        //先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。
        
        //然后确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。

        //然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins中选择一个硬币，然后目标金额就会减少
        
        // 最后明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：
        //print ("coinChange, amount=\(amount)")
        if amount == 0 {
            return (0, []);
        }
        if amount < 0 {
            return (-1, [])
        }
        
        
        var minCoinNum = -1;
        var minCoinArr:[Int] = [];
        var minCoinValue = -1;
        for coinValue in coins.reversed() {
            let restAmount = amount - coinValue;
            if restAmount < 0 {
                continue;
            }
            var minTuple = self.amount2minNumDic[restAmount];
            if minTuple == nil {
                minTuple  = self.coinChange(coins, restAmount);
            } else {
                //print ("find from Dic, minNum=\(minTuple!.0), restAmount=\(restAmount)")
            }
            let minNum = minTuple!.0;
            let subCoinArr = minTuple!.1;
            if minNum < 0 {
                continue;
            }
            if minCoinNum < 0 {
                minCoinNum = minNum;
                minCoinArr = subCoinArr;
                minCoinValue = coinValue;
                
                
            } else if minNum < minCoinNum {
                minCoinNum = minNum;
                minCoinArr = subCoinArr;
                minCoinValue = coinValue;
                
            }
        }
        
        if minCoinNum < 0 {
            self.amount2minNumDic[amount] = (-1, []);
            return (-1, []);
        }
        minCoinArr.insert(minCoinValue, at: 0);
        self.amount2minNumDic[amount] = (1+minCoinNum, minCoinArr);
        return (1+minCoinNum, minCoinArr);
    }
    
    /*
     有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

     现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

     求所能获得硬币的最大数量。

      

     示例 1：
     输入：nums = [3,1,5,8]
     输出：167
     解释：
     nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
     coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
     示例 2：

     输入：nums = [1,5]
     输出：10
      

     提示：

     n == nums.length
     1 <= n <= 300
     0 <= nums[i] <= 100

     链接：https://leetcode.cn/problems/burst-balloons

     */
    
    var dpIJKMaxCoin:[String:Int] = [:];
    
    var dpIJKMaxCoinArr:[Int] = [];
    var extendNums:[Int] = [];
    func maxCoins(_ nums: [Int]) -> Int {
        
        if nums.count == 0 {
            return 0;
        }
        if nums.count == 1 {
            return nums.first!;
        }
        if nums.count == 2 {
            return nums[0]*nums[1] + (nums[0] > nums[1] ? nums[0] : nums[1]);
        }
        
        // dp 函数 设计，dp[i][j] 表示按照某个顺序戳破i 和 j 之间气球能够获得的最大Coin 数
        // dp[i][j](k), 表示下标 i 和 j 之间(i 和 j 不能选，也就是k在i 和 j的开区间)，选取 k 做最后一个戳破的气球，如此得到的最大Coin 数
        // 因为 k最后被戳破，所以 最后一次获得的 Coin 为 nums[i]xnums[k]xnums[j]，k被戳破前，i到k开区间 按照某个顺序戳破能够获得的最大Coin 数 为 dp[i][k]，k到j开区间 为 dp[k][j]
        // 如此 dp[i][j](k) 的数值 = dp[i][k] + dp[k][j] + nums[i]xnums[k]xnums[j]
        // 遍历计算 所有可能的 k 值，取最大值。
        
        // 扩充 nums，在头尾加入 1 便于计算，extendNums 便于传值
        self.extendNums = nums;
        self.extendNums.insert(1, at: 0);
        self.extendNums.append(1);
        
        // 准备 dpIJKMaxCoin
        self.dpIJKMaxCoinArr = [];
        for i in 0..<self.extendNums.count {
            for j in 0..<self.extendNums.count {
                if i+1>=j {
                    self.dpIJKMaxCoinArr.append(0);
                } else {
                    self.dpIJKMaxCoinArr.append(-1);
                }
            }
        }
        
        let dpSize = self.extendNums.count;
        for i in stride(from: self.extendNums.count-3, through: 0, by: -1){
            for j in stride(from: i+2, through: self.extendNums.count-1, by: 1){
                var maxRtn = -1;
                for k in i+1..<j {
                    let left = self.dpIJKMaxCoinArr[i*dpSize + k];
                    let right = self.dpIJKMaxCoinArr[k*dpSize + j];
                    let sum = left + right + self.extendNums[i]*self.extendNums[k]*self.extendNums[j];
                    if sum > maxRtn {
                        maxRtn = sum;
                    }
                }
                self.dpIJKMaxCoinArr[i*dpSize + j] = maxRtn;
                
            }
        }
        let rtn = self.dpIJKMaxCoinArr[self.extendNums.count-1]; // i=0, j=self.extendNums.count-1
        return rtn;
    }
    
    func maxCoins5(_ nums: [Int]) -> Int {
        
        if nums.count == 0 {
            return 0;
        }
        if nums.count == 1 {
            return nums.first!;
        }
        if nums.count == 2 {
            return nums[0]*nums[1] + (nums[0] > nums[1] ? nums[0] : nums[1]);
        }
        
        // dp 函数 设计，dp[i][j] 表示按照某个顺序戳破i 和 j 之间气球能够获得的最大Coin 数
        // dp[i][j](k), 表示下标 i 和 j 之间(i 和 j 不能选，也就是k在i 和 j的开区间)，选取 k 做最后一个戳破的气球，如此得到的最大Coin 数
        // 因为 k最后被戳破，所以 最后一次获得的 Coin 为 nums[i]xnums[k]xnums[j]，k被戳破前，i到k开区间 按照某个顺序戳破能够获得的最大Coin 数 为 dp[i][k]，k到j开区间 为 dp[k][j]
        // 如此 dp[i][j](k) 的数值 = dp[i][k] + dp[k][j] + nums[i]xnums[k]xnums[j]
        // 遍历计算 所有可能的 k 值，取最大值。
        
        // 扩充 nums，在头尾加入 1 便于计算，extendNums 便于传值
        self.extendNums = nums;
        self.extendNums.insert(1, at: 0);
        self.extendNums.append(1);
        
        // 准备 dpIJKMaxCoin
        self.dpIJKMaxCoin = [:];
        for i in 0..<self.extendNums.count {
            for j in 0..<self.extendNums.count {
                if i+1>=j {
                    self.dpIJKMaxCoin["\(i)-\(j)"] = 0;
                } else {
                    //self.dpIJKMaxCoin["\(i)-\(j)"] = -1;
                }
            }
        }
        
        for i in stride(from: self.extendNums.count-3, through: 0, by: -1){
            for j in stride(from: i+2, through: self.extendNums.count-1, by: 1){
                var maxRtn = -1;
                for k in i+1..<j {
                    let left = self.dpIJKMaxCoin["\(i)-\(k)"];
                    let right = self.dpIJKMaxCoin["\(k)-\(j)"];
                    let sum = left! + right! + self.extendNums[i]*self.extendNums[k]*self.extendNums[j];
                    if sum > maxRtn {
                        maxRtn = sum;
                    }
                }
                self.dpIJKMaxCoin["\(i)-\(j)"] = maxRtn;
                
            }
        }
        let rtn = self.dpIJKMaxCoin["0-\(self.extendNums.count-1)"];
        return rtn!
        
        
        //return self.maxCoinsBetween(0, self.extendNums.count-1)
    }
    
    func maxCoinsBetween(_ i:Int, _ j:Int) -> Int {
        if let val = self.dpIJKMaxCoin["\(i)-\(j)"] {
            if val >= 0 {
                return val;
            }
        }
        
        var maxRtn = -1;
        for kIndex in stride(from: i+1, to: j, by: 1) {
            //dp[i][j](k) 的数值 = dp[i][k] + dp[k][j] + nums[i]xnums[k]xnums[j]
            let sum = self.maxCoinsBetween(i, kIndex) + self.maxCoinsBetween(kIndex, j) + self.extendNums[i]*self.extendNums[kIndex]*self.extendNums[j];
            if sum > maxRtn {
                maxRtn = sum;
            }
        }
        self.dpIJKMaxCoin["\(i)-\(j)"] = maxRtn;
        return maxRtn;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    var numArr2MaxCoin:[String:Int] = [:];
    func arrJoin(_ arr:[Int], _ separator:String) -> String {
        var rtnStr = "";
        for val in arr {
            if rtnStr.count > 0 {
                rtnStr += separator;
            }
            rtnStr += "\(val)";
        }
        return rtnStr
    }

    func maxCoins2(_ nums: [Int]) -> Int {
        // 递归 穷举，nums小的时候可行，nums 大的时候超时
        if nums.count == 0 {
            return 0;
        }
        if nums.count == 1 {
            return nums.first!;
        }
        if nums.count == 2 {
            return nums[0]*nums[1] + (nums[0] > nums[1] ? nums[0] : nums[1]);
        }

        let numArrStr = self.arrJoin(nums, "|");
        //let numArrStr = nums.joined(separator:"|");
        if let maxVal = self.numArr2MaxCoin[numArrStr] {
            return maxVal;
        }
        
        //
        var rtnMax = 0;
        var removeIndex = -1;
        var removeVal = -1;
        for firstRemoveIndex in 0..<nums.count {
            var left = firstRemoveIndex-1 < 0 ? 1 : nums[firstRemoveIndex-1];
            var right = firstRemoveIndex+1 == nums.count ? 1 : nums[firstRemoveIndex+1];
            var sum = left * nums[firstRemoveIndex] * right;

            var numsCopy = nums;
            numsCopy.remove(at:firstRemoveIndex);
            sum += maxCoins(numsCopy);

            if sum > rtnMax {
                removeIndex =  firstRemoveIndex;
                removeVal = nums[removeIndex];
                rtnMax = sum;
            }
        }
        if nums.count > 3 {
            print ("nums=\(nums), rtnMax=\(rtnMax), removeIndex=\(removeIndex) ,removeVal=\(removeVal)");
            //print ("numArr2MaxCoin=\(self.numArr2MaxCoin)");
        }
        self.numArr2MaxCoin[numArrStr] = rtnMax;
        return rtnMax;
    }
}
